<!DOCTYPE html>
<html lang=zh>
<head>
    <meta charset="utf-8">
    

    <meta name="baidu-site-verification" content="lt822VnP06" />
    <meta name="baidu-site-verification" content="0Ajixw1Puk" />
    <meta name="google-site-verification" content="gCQD0Y6f0YlPTZTAjp_mqms4C7TlkMWrg3Xy0mFdMwI" />
    <title>[译]Java 8中HashMap和LinkedHashMap如何解决冲突 | Giraffe&#39;s Home</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
    <meta name="description" content="原文来自一个java大牛的博客 原文地址http://javarevisited.blogspot.jp/2016/01/how-does-java-hashmap-or-linkedhahsmap-handles.html 博客讲解了Java 8中HashMap和LinkedHashMap是如何解决冲突的。">
<meta property="og:type" content="article">
<meta property="og:title" content="[译]Java 8中HashMap和LinkedHashMap如何解决冲突">
<meta property="og:url" content="http://yemengying.com/2016/02/03/译-Java中HashMap和LinkedHashMap如何解决冲突/index.html">
<meta property="og:site_name" content="Giraffe's Home">
<meta property="og:description" content="原文来自一个java大牛的博客 原文地址http://javarevisited.blogspot.jp/2016/01/how-does-java-hashmap-or-linkedhahsmap-handles.html 博客讲解了Java 8中HashMap和LinkedHashMap是如何解决冲突的。">
<meta property="og:image" content="http://yemengying.com/images/thumbnail7.jpg">
<meta property="og:updated_time" content="2017-06-10T07:56:03.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="[译]Java 8中HashMap和LinkedHashMap如何解决冲突">
<meta name="twitter:description" content="原文来自一个java大牛的博客 原文地址http://javarevisited.blogspot.jp/2016/01/how-does-java-hashmap-or-linkedhahsmap-handles.html 博客讲解了Java 8中HashMap和LinkedHashMap是如何解决冲突的。">
<meta name="twitter:image" content="http://yemengying.com/images/thumbnail7.jpg">
    

    

    
        <link rel="icon" href="https://yemengying.com/qiniu/image/image/favicon.png" />
    


    <link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
    <link rel="stylesheet" href="/lib/open-sans/styles.css">
    <link rel="stylesheet" href="/lib/source-code-pro/styles.css">

    <link rel="stylesheet" href="/css/style.css">

    <script src="/lib/jquery/2.1.3/jquery.min.js"></script>
    
    
        <link rel="stylesheet" href="/lib/fancybox/jquery.fancybox.css">
    
    
        <script type="text/javascript">
(function(i,s,o,g,r,a,m) {i['GoogleAnalyticsObject']=r;i[r]=i[r]||function() {
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

ga('create', 'UA-75861791-1', 'auto');
ga('send', 'pageview');

</script>
    
    
    
        <script>
var _hmt = _hmt || [];
(function() {
    var hm = document.createElement("script");
    hm.src = "//hm.baidu.com/hm.js?44bb8bfb1a576270255713e37746eb82";
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(hm, s);
})();
</script>

    

</head>
<body>
    <script src="//github.elemecdn.com/jiananshi/req/0.1.0/lib/req.js"></script>
    <script src="//npm.elemecdn.com/jinkela@1.2.18/umd.js"></script>
    <script src="//github.elemecdn.com/jiananshi/DisqusJS/2.0.8/index.js"></script>
    <div id="container">
        <header id="header">
    <div id="header-main" class="header-inner">
        <div class="outer">
            <a href="/" id="logo">
                <i class="logo"></i>
                <span class="site-title">Giraffe&#39;s Home</span>
            </a>
            <nav id="main-nav">
                
                    <a class="main-nav-link" href="/.">首页</a>
                
                    <a class="main-nav-link" href="/archives">归档</a>
                
                    <a class="main-nav-link" href="/categories">分类</a>
                
                    <a class="main-nav-link" href="/tags">标签</a>
                
                    <a class="main-nav-link" href="/about">关于</a>
                
                    <a class="main-nav-link" href="/message">留言</a>
                
                    <a class="main-nav-link" href="/friends">友链</a>
                
                    <a class="main-nav-link" href="/reading">正在读...</a>
                
            </nav>
            
                
                <nav id="sub-nav">
                    <div class="profile" id="profile-nav">
                        <a id="profile-anchor" href="javascript:;">
                            <img class="avatar" src="https://pic.yupoo.com/jiananshi/e85e4303/735cf286.jpeg" />
                            <i class="fa fa-caret-down"></i>
                        </a>
                    </div>
                </nav>
            
            <div id="search-form-wrap">

    <form class="search-form">
        <input type="text" class="ins-search-input search-form-input" placeholder="搜索" />
        <button type="submit" class="search-form-submit"></button>
    </form>
    <div class="ins-search">
    <div class="ins-search-mask"></div>
    <div class="ins-search-container">
        <div class="ins-input-wrapper">
            <input type="text" class="ins-search-input" placeholder="想要查找什么..." />
            <span class="ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
            UNTITLED: '(未命名)',
        },
        ROOT_URL: '/',
        CONTENT_URL: '/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>
<script src="/js/insight.js"></script>

</div>
        </div>
    </div>
    <div id="main-nav-mobile" class="header-sub header-inner">
        <table class="menu outer">
            <tr>
                
                    <td><a class="main-nav-link" href="/.">首页</a></td>
                
                    <td><a class="main-nav-link" href="/archives">归档</a></td>
                
                    <td><a class="main-nav-link" href="/categories">分类</a></td>
                
                    <td><a class="main-nav-link" href="/tags">标签</a></td>
                
                    <td><a class="main-nav-link" href="/about">关于</a></td>
                
                    <td><a class="main-nav-link" href="/message">留言</a></td>
                
                    <td><a class="main-nav-link" href="/friends">友链</a></td>
                
                    <td><a class="main-nav-link" href="/reading">正在读...</a></td>
                
                <td>
                    
    <div class="search-form">
        <input type="text" class="ins-search-input search-form-input" placeholder="搜索" />
    </div>

                </td>
            </tr>
        </table>
    </div>
</header>

        <div class="outer">
            
                

<aside id="profile">
    <div class="inner profile-inner">
        <div class="base-info profile-block">
            <img id="avatar" src="https://pic.yupoo.com/jiananshi/e85e4303/735cf286.jpeg" />
            <h2 id="name">Giraffe</h2>
            <h3 id="title">Java Developer</h3>
            <span id="location"><i class="fa fa-map-marker"></i>Shanghai, China</span>
            <a id="follow" target="_blank" href="https://github.com/giraffe0813/">关注我</a>
        </div>
        <div class="article-info profile-block">
            <div class="article-info-block">
                56
                <span>文章</span>
            </div>
            <div class="article-info-block">
                36
                <span>标签</span>
            </div>
        </div>
        <div class="profile-block recent-comments">
            <p class="recent-comments-title">最新评论</p>
            <ul id="disqus-recent-comments" class="recent-comments-container">
            </ul>
        </div>
        
        <div class="profile-block social-links">
            <table>
                <tr>
                    
                    
                    <td>
                        <a href="http://github.com/giraffe0813" target="_blank" title="github" class=tooltip>
                            <i class="fa fa-github"></i>
                        </a>
                    </td>
                    
                    <td>
                        <a href="/atom.xml" target="_blank" title="rss" class=tooltip>
                            <i class="fa fa-rss"></i>
                        </a>
                    </td>
                    
                </tr>
            </table>
        </div>
        
    </div>
</aside>

            
            <section id="main"><article id="2016/02/03/译-Java中HashMap和LinkedHashMap如何解决冲突/" class="article article-type-post" itemscope itemprop="blogPost">
    <div class="article-inner">
        
        
        
            <header class="article-header">
                
    
        <h1 class="article-title" itemprop="name">
            [译]Java 8中HashMap和LinkedHashMap如何解决冲突
        </h1>
    

                <div class="article-meta">
                    
    <div class="article-date">
        <i class="fa fa-calendar"></i>
        <a href="/2016/02/03/译-Java中HashMap和LinkedHashMap如何解决冲突/">
            <time datetime="2016-02-03T08:23:39.000Z" itemprop="datePublished">2016-02-03</time>
        </a>
    </div>


                    
    <div class="article-category">
    	<i class="fa fa-folder"></i>
        <a class="article-category-link" href="/categories/java/">java</a><i class="fa fa-angle-right"></i><a class="article-category-link" href="/categories/java/hashmap/">hashmap</a>
    </div>

                    
    <div class="article-tag">
        <i class="fa fa-tag"></i>
        <a class="tag-link" href="/tags/java/">java</a>, <a class="tag-link" href="/tags/翻译/">翻译</a>
    </div>

                </div>
            </header>
        
        <div class="article-entry" itemprop="articleBody">
        
            
                <div id="toc" class="toc-article">
                <strong class="toc-title">文章目录</strong>
                    <ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#什么时候会产生冲突"><span class="toc-number">1.</span> <span class="toc-text">什么时候会产生冲突</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#总结"><span class="toc-number">2.</span> <span class="toc-text">总结</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#相关阅读"><span class="toc-number">3.</span> <span class="toc-text">相关阅读</span></a></li></ol>
                </div>
            
            <blockquote>
<p>原文来自一个java大牛的博客 原文地址<a href="http://javarevisited.blogspot.jp/2016/01/how-does-java-hashmap-or-linkedhahsmap-handles.html" target="_blank" rel="external">http://javarevisited.blogspot.jp/2016/01/how-does-java-hashmap-or-linkedhahsmap-handles.html</a> 博客讲解了Java 8中HashMap和LinkedHashMap是如何解决冲突的。</p>
</blockquote>
<a id="more"></a>
<p>在Java 8 之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。为了解决在频繁冲突时hashmap性能降低的问题，Java 8中使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。<br>在Java 8中使用常量<strong>TREEIFY_THRESHOLD</strong>来控制是否切换到平衡树来存储。目前，这个常量值是8，这意味着当有超过8个元素的索引一样时，HashMap会使用树来存储它们。<br>这一改变是为了继续优化常用类。大家可能还记得在Java 7中为了优化常用类对ArrayList和HashMap采用了延迟加载的机制，在有元素加入之前不会分配内存，这会减少空的链表和HashMap占用的内存。<br>这一动态的特性使得HashMap一开始使用链表，并在冲突的元素数量超过指定值时用平衡二叉树替换链表。不过这一特性在所有基于hash table的类中并没有，例如Hashtable和WeakHashMap。<br>目前，只有<strong>ConcurrentHashMap</strong>,<strong>LinkedHashMap</strong>和<strong>HashMap</strong>会在频繁冲突的情况下使用平衡树。</p>
<h3 id="什么时候会产生冲突"><a href="#什么时候会产生冲突" class="headerlink" title="什么时候会产生冲突"></a>什么时候会产生冲突</h3><p>HashMap中调用<strong>hashCode()</strong>方法来计算hashCode。<br>由于在Java中两个不同的对象可能有一样的hashCode,所以不同的键可能有一样hashCode，从而导致冲突的产生。</p>
<h3 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h3><ul>
<li>HashMap在处理冲突时使用链表存储相同索引的元素。</li>
<li>从Java 8开始，HashMap，ConcurrentHashMap和LinkedHashMap在处理频繁冲突时将使用平衡树来代替链表，当同一hash桶中的元素数量超过特定的值便会由链表切换到平衡树，这会将get()方法的性能从O(n)提高到O(logn)。</li>
<li>当从链表切换到平衡树时，HashMap迭代的顺序将会改变。不过这并不会造成什么问题，因为HashMap并没有对迭代的顺序提供任何保证。</li>
<li>从Java 1中就存在的Hashtable类为了保证迭代顺序不变，即便在频繁冲突的情况下也不会使用平衡树。这一决定是为了不破坏某些较老的需要依赖于Hashtable迭代顺序的Java应用。</li>
<li>除了Hashtable之外，WeakHashMap和IdentityHashMap也不会在频繁冲突的情况下使用平衡树。</li>
<li>使用HashMap之所以会产生冲突是因为使用了键对象的hashCode()方法，而equals()和hashCode()方法不保证不同对象的hashCode是不同的。需要记住的是，相同对象的hashCode一定是相同的，但相同的hashCode不一定是相同的对象。</li>
<li>在HashTable和HashMap中，冲突的产生是由于不同对象的hashCode()方法返回了一样的值。</li>
</ul>
<p>以上就是Java中HashMap如何处理冲突。这种方法被称为链地址法，因为使用链表存储同一桶内的元素。通常情况HashMap，HashSet，LinkedHashSet，LinkedHashMap，ConcurrentHashMap，HashTable，IdentityHashMap和WeakHashMap均采用这种方法处理冲突。</p>
<p>从JDK 8开始，HashMap，LinkedHashMap和ConcurrentHashMap为了提升性能，在频繁冲突的时候使用平衡树来替代链表。因为HashSet内部使用了HashMap，LinkedHashSet内部使用了LinkedHashMap，所以他们的性能也会得到提升。</p>
<h3 id="相关阅读"><a href="#相关阅读" class="headerlink" title="相关阅读"></a>相关阅读</h3><p><a href="http://www.amazon.com/Data-Structures-Algorithms-Michael-Goodrich/dp/0470383267?tag=javamysqlanta-20" target="_blank" rel="external">Data Structure and Algorithm in Java</a><br><a href="http://www.amazon.com/Java-Performance-The-Definitive-Guide/dp/1449358454?tag=javamysqlanta-20" target="_blank" rel="external">Java Performance The Definitive Guide</a></p>

        
        </div>
        <footer class="article-footer">
            <div class="share-container">



</div>

    <a data-url="http://yemengying.com/2016/02/03/译-Java中HashMap和LinkedHashMap如何解决冲突/" data-id="cjtvbucjp004cz15sjhkc879p" class="article-share-link"><i class="fa fa-share"></i>分享到</a>
<script>
    (function ($) {
        // Prevent duplicate binding
        if (typeof(__SHARE_BUTTON_BINDED__) === 'undefined' || !__SHARE_BUTTON_BINDED__) {
            __SHARE_BUTTON_BINDED__ = true;
        } else {
            return;
        }
        $('body').on('click', function() {
            $('.article-share-box.on').removeClass('on');
        }).on('click', '.article-share-link', function(e) {
            e.stopPropagation();

            var $this = $(this),
                url = $this.attr('data-url'),
                encodedUrl = encodeURIComponent(url),
                id = 'article-share-box-' + $this.attr('data-id'),
                offset = $this.offset(),
                box;

            if ($('#' + id).length) {
                box = $('#' + id);

                if (box.hasClass('on')){
                    box.removeClass('on');
                    return;
                }
            } else {
                var html = [
                    '<div id="' + id + '" class="article-share-box">',
                        '<input class="article-share-input" value="' + url + '">',
                        '<div class="article-share-links">',
                            '<a href="https://twitter.com/intent/tweet?url=' + encodedUrl + '" class="fa fa-twitter article-share-twitter" target="_blank" title="Twitter"></a>',
                            '<a href="https://www.facebook.com/sharer.php?u=' + encodedUrl + '" class="fa fa-facebook article-share-facebook" target="_blank" title="Facebook"></a>',
                            '<a href="http://pinterest.com/pin/create/button/?url=' + encodedUrl + '" class="fa fa-pinterest article-share-pinterest" target="_blank" title="Pinterest"></a>',
                            '<a href="https://plus.google.com/share?url=' + encodedUrl + '" class="fa fa-google article-share-google" target="_blank" title="Google+"></a>',
                        '</div>',
                    '</div>'
                ].join('');

              box = $(html);

              $('body').append(box);
            }

            $('.article-share-box.on').hide();

            box.css({
                top: offset.top + 25,
                left: offset.left
            }).addClass('on');

        }).on('click', '.article-share-box', function (e) {
            e.stopPropagation();
        }).on('click', '.article-share-box-input', function () {
            $(this).select();
        }).on('click', '.article-share-box-link', function (e) {
            e.preventDefault();
            e.stopPropagation();

            window.open(this.href, 'article-share-box-window-' + Date.now(), 'width=500,height=450');
        });
    })(jQuery);
</script>

            
    
        <a href="http://yemengying.com/2016/02/03/译-Java中HashMap和LinkedHashMap如何解决冲突/#comments" class="article-comment-link disqus-comment-count" data-disqus-url="http://yemengying.com/2016/02/03/译-Java中HashMap和LinkedHashMap如何解决冲突/">评论</a>
    

        </footer>
    </div>
    
        
<nav id="article-nav">
    
        <a href="/2016/02/20/Java-8-行为参数化-behavior-parameterization/" id="article-nav-newer" class="article-nav-link-wrap">
            <strong class="article-nav-caption">上一篇</strong>
            <div class="article-nav-title">
                
                    Java 8 --行为参数化(behavior parameterization)
                
            </div>
        </a>
    
    
        <a href="/2016/01/19/最近看的书/" id="article-nav-older" class="article-nav-link-wrap">
            <strong class="article-nav-caption">下一篇</strong>
            <div class="article-nav-title">最近看的书</div>
        </a>
    
</nav>


    
    <script>
   DisqusJS.getArticleComments();
   </script>
</article>


    
    <section id="comments">
    
        
    <div id="disqus_thread">
        <noscript>Please enable JavaScript to view the <a href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
    </div>

    
    </section>

</section>
            
        </div>
        <footer id="footer">
    <div class="outer">
        <div id="footer-info" class="inner">
            &copy; 2019 Mengying Ye<br>
            Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
        </div>
    </div>
</footer>
        
    
   <script>
   DisqusJS.getRecentComments(document.querySelector('#disqus-recent-comments'));
   </script>



    
        <script src="/lib/fancybox/jquery.fancybox.pack.js"></script>
    


<!-- Custom Scripts -->
<script src="/js/main.js"></script>

    </div>
</body>
</html>
